In data communication as in storage applications, encoding of an incoming data byte stream into an equivalent stream of code words is often performed for reasons of better use of the transmission channel, facilitating receiver operations, safer transmission or storage, better recognition of noisy transmitted or stored data, lower failure rate under difficult conditions, etc. At very high data speeds, e.g. in the Gigabit-per-second area, it becomes difficult to encode the incoming data byte stream fast enough, even more so when complex encoding methods or schemes are being used. One of the preferred encoding methods includes the use of finite-state encoders that have to be state-updated after each encoding step. If such finite-state encoders are arranged in parallel to adapt them to high data rates in a pipelining fashion, the state-updating still occurs sequentially, thus often requiring more time than available. Of course, this slows down the maximum transmission speed achievable with such a device.
European Patent Application 90810614.9, filed Aug. 16, 1990, not yet published, shows one approach to solve the problem indicated above and persons skilled in the art may derive useful background information and some details for understanding the present invention. In the prior application, an encoder principle is disclosed which allows pipelined as well as seemingly parallel operation of the encoder. Several finite-state coder units are physically arranged in parallel, however, the respective coder state updating bits are actually not simultaneously available, but propagate from section to section similar to a carry-over function. Though this propagation may happen within one clock cycle, it certainly determines the minimum length of such clock cycle and thus limits the achievable speed for processing incoming data strings.
General methods introducing concurrency to improve the throughput at the expense of latency are described by H.-D. Lin and D.G. Messerschmitt in "Finite State Machine has Unlimited Concurrency", published in the IEEE Transactions on Circuits and Systems, Vol. 38, No. 5, May 1991. The methods described there are, however, of very general and more theoretical nature and do not teach or address how to efficiently generate concurrency in a given specific application.